//【模板】Floyd:https://www.luogu.com.cn/problem/B3647

#include <iostream>
#include <cstring>

using namespace std;
const int N = 110,M=4510;

int edges[N][N];
int n,m;

void floyd()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                edges[i][j] = min(edges[i][j],edges[i][k]+edges[k][j]);
            }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            cout << edges[i][j] << ' ';
        cout << endl;
    }
}

int main()
{
    memset(edges,0x3f,sizeof edges);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        edges[i][i] = 0;
    }
    for(int i = 1; i <= m; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        edges[u][v] = edges[v][u] = min(edges[u][v],w);
    }
    floyd();
    return 0;
}